package hu.arguscab.ai;

import java.util.Iterator;
import java.util.Stack;

/**
 * An iterator which iterate from leaves upwards.<br>
 *&nbsp&nbsp&nbsp A       Order of the iteration is: G, F, E, D, C, B, A <br>
 *&nbsp&nbsp/ &nbsp \<br>
 *&nbspB &nbsp &nbsp &nbspC<br>
 * / \ &nbsp &nbsp/ &nbsp\<br>
 *     D&nbsp&nbspE&nbsp&nbspF  G<br>
 * @param <E> The data type that <code>Edge</code> contain. 
 * @param <N> The data type that <code>Node</code> contain. 
 * @author sharp
 */
public class LeafFirstIterator<E, N> extends TreeIterable<E, N> {


	public LeafFirstIterator(Tree<E, N> tree) {
		super(tree);
	}

	@Override
	public Iterator<Node<N>> iterator() {
		return new LeafFirstIteratorImpl<E, N>(getTree());
	}
}

class LeafFirstIteratorImpl<E, N> implements Iterator<Node<N>> {

	Stack<Node<N>> stack;

	public LeafFirstIteratorImpl(Tree<E, N> tree) {
		stack = new Stack<Node<N>>();
		// Leaves are pushed to the top of the stack
		for ( Node<N> n : tree.breathSearchIterator() ) {
			stack.push((Node<N>) n);
		}
		
	}

	@Override
	public boolean hasNext() {
		return stack.size() > 0;
	}

	@Override
	public Node<N> next() {
		return stack.pop();
	}

	@Override
	public void remove() {
		throw new UnsupportedOperationException("Not supported yet.");		
	}
	
}
